Q: Which of the following is false about a binary search tree?
A. The left child is always lesser than its parent
B. The right child is always greater than its parent
C. The left and right sub-trees should also be binary search trees
D. In order sequence gives decreasing order of elements
Solution: In order sequence of binary search trees will always give ascending order of elements. Remaining all are true regarding binary search trees.
Q: How to search for a key in a binary search tree?
A. public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}
B. public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.left,key);
}
else
return search(root.right,key);
}
C. public Tree search(Tree root, int key)
{
if( root == null)
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}
D. public Tree search(Tree root, int key)
{
if( root == null)
{
return root;
}
if( root.key < key )
{
return search(root.right.right,key);
}
else
return search(root.left.left,key);
}
Solution: As we know that the left child is lesser than the parent, if the root’s key is greater than the given key, we look only into the left sub-tree, similarly for right sub-tree.
Q: What are the conditions for an optimal binary search tree and what is its advantage?
A. The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
B. You should know the frequency of access of the keys, improves the lookup time
C. The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time
D. The tree should be just modified and improves the lookup time
Solution: For an optimal binary search The tree should not be modified and we need to find how often keys are accessed. Optimal binary search improves the lookup cost.
Q: What does the following piece of code do?
public void func(Tree root)
{
System.out.println(root.data());
func(root.left());
func(root.right());
}
A. Preorder traversal
B. Inorder traversal
C. Postorder traversal
D. Level order traversal
Solution: In a preorder traversal, first the parent is visited, then the left child and finally the right child.
Q: What is the speciality about the inorder traversal of a binary search tree?
A. It traverses in a non increasing order
B. It traverses in an increasing order
C. It traverses in a random fashion
D. It traverses based on priority of the node
Solution: As a binary search tree consists of elements lesser than the node to the left and the ones greater than the node to the right, an inorder traversal will give the elements in an increasing order.
Q: What does the following piece of code do?
public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
}
A. Preorder traversal
B. Inorder traversal
C. Postorder traversal
D. Level order traversal
Solution: In a postorder traversal, first the left child is visited, then the right child and finally the parent.
Q: How will you find the minimum element in a binary search tree?
A. public void min(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}
B. public void min(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}
C. public void min(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}
D. public void min(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
}
Solution: Since all the elements lesser than a given node will be towards the left, iterating to the leftmost leaf of the root will give the minimum element in a binary search tree.
Q: How will you find the maximum element in a binary search tree?
A. public void max(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}
B. public void max(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}
C. public void max(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}
D. public void max(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
}
Solution: Since all the elements greater than a given node are towards the right, iterating through the tree to the rightmost leaf of the root will give the maximum element in a binary search tree.
Q: What are the worst case and average case complexities of a binary search tree?
A. O(n), O(n)
B. O(logn), O(logn)
C. O(logn), O(n)
D. O(n), O(logn)
Solution: Worst case arises when the tree is skewed(either to the left or right) in which case you have to process all the nodes of the tree giving O(n) complexity, otherwise O(logn) as you process only the left half or the right half of the tree.
Q: Given that 2 elements are present in the tree, write a function to find the LCA(Least Common Ancestor) of the 2 elements.
A. public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.right();
else if (root.data() < n1 && root.data() < n2)
root = root.left();
else break;
}
System.out.println(root.data());
}
B. public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() < n2)
root = root.left();
else if (root.data() < n1 && root.data() > n2)
root = root.right();
else break;
}
System.out.println(root.data());
}
C. public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.left();
else if (root.data() < n1 && root.data() < n2)
root = root.right();
else break;
}
System.out.println(root.data());
}
D. public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.left.left();
else if (root.data() < n1 && root.data() < n2)
root = root.right.right();
else break;
}
System.out.println(root.data());
}
Solution: The property of a binary search tree is that the lesser elements are to the left and greater elements are to the right, we use this property here and iterate through the tree such that we reach a point where the 2 elements are on 2 different sides of the node, this becomes the least common ancestor of the 2 given elements.